package _17_graph;

import org.junit.Test;

import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/25 - 20:30
 * 贝尔曼·福特 算法，检测负环
 * 参照图片 img/负环情况.png
 */
public class Bellmanford2 {
    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.edges = List.of(new Edge(v2, 2));
        v2.edges = List.of(new Edge(v3, -4));
        v3.edges = List.of(new Edge(v1, 1), new Edge(v4, 1));
        v4.edges = List.of();
        List<Vertex> graph = List.of(v1, v2, v3, v4);

        bellmanford(v1, graph);

        for (Vertex vertex : graph) {
            System.out.println(vertex);
        }
    }

    private void bellmanford(Vertex source, List<Vertex> graph) {
        source.dist = 0;
        // 遍历次数 = size-1
        int size = graph.size();
        for (int i = 0; i < size; i++) {
            for (Vertex vertex : graph) {
                for (Edge edge : vertex.edges) {
                    Vertex linked = edge.linked;
                    if (vertex.dist != Integer.MAX_VALUE && vertex.dist + edge.weight < linked.dist) {
                        if (i == size - 1) {
                            // 遍历次数用尽，顶点的最短路径还可以更新，就说明出现了负环
                            throw new RuntimeException("出现负环");
                        }
                        linked.dist = vertex.dist + edge.weight;
                        linked.prev = vertex;
                    }
                }
            }
        }
    }
}
